#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if (nums.size() < 2) {
            return nums.size();
        }
        set<pair<int, int>> set;
        int max_len = 1;
        set.insert({nums[nums.size() - 1], 1});
        for (int i = nums.size() - 2; i >= 0; i--) {
            if (nums[i] < set.begin()->first) {
                int len = set.begin()->second + 1;
                set.insert({nums[i], len});
                max_len = max(max_len, len);
            } else {
                auto it = upper_bound(set.begin(), set.end(), pair{nums[i], 0});
                set.insert({nums[i], it->second + 1});
                max_len = max(max_len, it->second + 1);
            }
        }
        return max_len;
    }
};

int main() {
    vector<int> input = {1,3,6,7,9,4,10,5,6};
    Solution solution;
    int output = solution.lengthOfLIS(input);
    cout << output << endl;
}